Communications networks, such as the Internet, employ addressing information in a packet header to forward the packet between networks towards the destination node. Typically, routing information is hierarchical in nature such that a destination address will include the address of the network and any sub-networks that host the destination node. This hierarchical routing information is similar to a 10 digit telephone number in which the first three digits identify the area code of a service area, the second three a specific switch in the area and the last four an end user serviced by the switch. Thus, when a call is placed by a call originator the switch to which the caller is connected need only determine the area code in order to direct the call to the appropriate area of the country. Similarly, a router often looks at the hierarchical routing information in an IP address to determine a next hop rather than concern itself with the complete address of the destination node. Unlike telephone numbers, the lengths of the prefixes in IP addresses are not fixed, making the lookup more complicated.
As the expectations of Internet services increase so too does the requirement to improve bandwidth. There are many factors affecting the speed at which data flows through the Internet, such as line rates, data quality of service, etc. One main factor dictating performance is the time taken in routing decisions. While improving routing decisions may not add significantly to the overall service delivery for low-speed dial up services where the line rate is typically the bottle neck, the speed of routing decisions becomes the limiting factor to bandwidth on faster transmission media, such as optical links, hence, the justification for this algorithm.
As the number of users of the Internet increases, so too does the demand for unique addresses. As a result, the IPv4 32 bit address space, which provide up to 2^23 unique addresses, is being rapidly exhausted. Techniques such as Network Address Translation have been proposed to extend the usability of the IPv4 address space, but these solutions break transparent end-to-end connectivity. IPv6, having a 128 bit address field, has been introduced in part to improve the address space issue.
The net result of the increased address header is that each router must look at, potentially, a much longer address in order to make a routing decision. Additionally, the ability to address more nodes means that IPv6 routing tables could potentially contain more routes than were possible with IPv4.
As indicated previously, the hierarchical addressing scheme enables a router to group nodes into networks. This reduces the number of entries in the routers forwarding tables, as a router can make a routing decision based on matching only the network part, prefix, of an address and not the entire address.
Prefix matching involves comparing part of an address with entries in a routing table. An exact match algorithm will, of course, give the best routing information quickly but typically such a search will require tables which are impractically large and difficult to update. A technique in which the longest prefix match is determined has evolved as a solution.
As routers forward at higher speeds, the time-efficiency of the forwarding algorithm can make a significant impact on the performance of the system. More efficient algorithms such as the one provided by this invention will allow higher system throughput to be achieved.
It should be noted that this algorithm is intended for IPv6 but there is no reason why it could not be used for IPv4 or any other application requiring an LPM search.
The prior art relating to IP routing lookups includes U.S. Pat. No. 6,018,524 which issued Jan. 25, 2000 to Turner et al. The Turner et al. patent discloses an algorithm that performs a binary search on prefix lengths using hash tables. In order to facilitate a binary search with a hash table, markers must be inserted in the hash table to indicate the presence of entries at longer prefix lengths in the routing table. Markers provide an indication that there is a longer prefix in the table which could provide a better match and could also contain the next hop information for a shorter prefix which would have been found had the current lookup resulted in a miss. These markers can occupy a significant portion of the hash tables, and can account for 10% to 60% (30% typical) of the contents of the hash table, resulting in more frequent hash collisions. In the case of IPv6, using this algorithm could require up to seven hash lookups, excluding collisions. There are additional schemes that could be used to marginally reduce the number of hash lookups at the cost of additional processing and additional tables.
A second prior art scenario is described by Dharmapurikar et al. entitled “Longest Prefix Matching Using Bloom Filters”. This paper was presented at SIGCOMM 03, Aug. 25-29 2003 in Karlsruhe Germany. The paper describes the use of a set of filters (hash functions) to determine in which set of prefix lengths an address belongs. The set of lengths is then searched in a hash table in linear order. In order to determine which prefix lengths are possible for a particular address one filter must be used for each prefix length that exists in the routing table. To allow for any possible routing table for IPv6, 128 filters must exist. In order to perform the filtering efficiently, this algorithm is limited to hardware implementation with large transistor/gate count to achieve a desirable level of processing parallelism.
Performing hash lookups is a costly operation, especially for IPv6. A hash function needs to be applied to the key, and a portion of the result is used to index an entry in memory. Since hashing is not a one-to-one mapping, collisions must be detected, which requires storing the original 16 byte (128 bit) IPv6 address, or a portion of it, in each hash table entry. Collisions could be resolved in a number of ways, but they typically require additional memory accesses, and additional information in each hash entry. In total, this is roughly 20 bytes of pure overhead that must be loaded at every hash lookup. As a result of the properties of using a hash table, the goal is to reduce the number of hash lookups, and the number of hash entries.
The majority of other IP forwarding algorithms which presently exist are tree based. Thus, their performance characteristics depend directly on the number of bits in the address and the number of entries in the routing table. Due to the length of the IPv6 address, existing tree based IPv4 forwarding algorithms do not scale up to IPv6 size addresses well in terms of memory storage and memory accesses. Using these algorithms would result in an explosion of the size of routing table data structures and an increase in the number of memory latencies needed to perform the look up. Additionally, existing look-up algorithms do not take advantage of several properties of IPv6 addresses that were designed to make IPv6 forwarding simpler such as hierarchical addressing. In fact, these IPv6 addressing properties are more likely to reduce the performance of existing IPv4 look up algorithms rather than increase in it.